package com.lw.leetcode.binary.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * binay
 * 1054. 距离相等的条形码
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/23 16:45
 */
public class RearrangeBarcodes {

    public static void main(String[] args) {
        RearrangeBarcodes test = new RearrangeBarcodes();



        //[2,1,2,1,2,1]
        int[] arr = {1,1,1,2,2,2};

        // [1,3,1,3,2,1,2,1]
//        int[] arr = {1,1,1,1,2,2,3,3};

        // [1, 3, 1, 3, 1, 2, 1, 2, 1]
//        int[] arr = {1,1,1,1,2,2,3,3, 1};

        int[] ints = test.rearrangeBarcodes(arr);
        System.out.println(Arrays.toString(ints));
    }


    private int[] barcodes;
    private int length;
    private int f;
    private int count;
    private int index;
    public int[] rearrangeBarcodes(int[] barcodes) {
        this.barcodes = barcodes;
        this.length = barcodes.length;
        this.f = (length ) >> 1;

        find(0, length - 1);
        int[] arr = new int[length];
        int t = barcodes[index];
        int i = 0;
        int c = count;
        while (c > 0) {
            arr[i] = t;
            i+= 2;
            c--;
        }
        if (i >= length) {
            i = 1;
        }
        if (index - count + 2 <= length - index) {
            c = index - count;
            while (c >= 0) {
                arr[i] = barcodes[c];
                c--;
                i += 2;
                if (i >= length) {
                    i = 1;
                }
            }
            c = index + 1;
            while (c < length) {
                arr[i] = barcodes[c];
                c++;
                i += 2;
                if (i >= length) {
                    i = 1;
                }
            }
        } else {
            c = index + 1;
            while (c < length) {
                arr[i] = barcodes[c];
                c++;
                i += 2;
                if (i >= length) {
                    i = 1;
                }
            }
            c = index - count;
            while (c >= 0) {
                arr[i] = barcodes[c];
                c--;
                i += 2;
                if (i >= length) {
                    i = 1;
                }
            }
        }
        return arr;
    }

    private void find (int st, int end ) {
        int s1 = st;
        int s2 = end;
        int t = barcodes[st];
        int count = 1;
        while (st < end) {
            int item = barcodes[st + 1];
            if (item == t) {
                st++;
                count++;
            } else if (item < t) {
                barcodes[st + 1] = barcodes[st - count + 1];
                barcodes[st - count + 1] = item;
                st++;
            } else {
                barcodes[st + 1] = barcodes[end];
                barcodes[end] = item;
                end--;
            }
        }
        if (st + 1 <= f ) {
            find(st + 1, s2);
        } else if (st - count + 1 > f) {
            find(s1, st - count);
        } else {
            this.count = count;
            this.index = st;
        }
    }

}
